// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 * Creator: yanking
 * Create time: 2022-02-25 12:14
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.leetCode.ValidPath;

import java.util.HashSet;

public class validPath {
    // 给定路径判断图中两个节点是否连通
    HashSet<Integer> node = new HashSet<>();

    public boolean validPath(int n, int[][] edges, int source, int destination) {
        // DFS 遍历,当遍历到destination节点的时候直接返回true
        // DFS遍历不适合访问双向图
        // 使用回溯保存已经走过的节点
        // 使用矩阵表示路径
        if (n == 1) {
            return true;
        }
        int[][] path = new int[n][n];

        for (int i = 0; i < edges.length; i++) {
            // 初始化路径信息
            path[edges[i][0]][edges[i][1]] = 1;
            path[edges[i][1]][edges[i][0]] = 1;
        }
        node.add(source);
        return DFS(n, path, source, destination);
    }

    public boolean DFS(int n, int[][] path, int source, int destination) {
        // 根据给定的路径和起点和终点，通过递归的方式判断两点之间是否存在路径
        if (path[source][destination] == 1) {
            // 两点之间没有间隔点且存在连接线
            return true;
        }
        for (int i = 0; i < n; i++) {
            if (node.contains(i)) continue;
            if (path[source][i] == 1) {
                node.add(i);
                if (DFS(n, path, i, destination)) {
                    return true;
                }
            }
        }
        return false;
    }
}
